
package jtg.parser;

import java.util.*;

public class PrefixExpressionParser {
    private int nodeId = 0;

    public ExpressionNode parse(String expression) {
        if (expression == null || expression.isEmpty()) {
            return null;
        }

        // 去掉外层的括号并按空格分割
        String[] tokens = expression.replaceAll("^\\(|\\)$", "").split("\\s+");
        Queue<String> queue = new LinkedList<>(Arrays.asList(tokens));

        return parseRecursive(queue);
    }

    private ExpressionNode parseRecursive(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }

        String token = queue.poll();
        ExpressionNode node = new ExpressionNode(token, nodeId++);

        if (isOperator(token)) {
            while (!queue.isEmpty() && !queue.peek().equals(")")) {
                node.addChild(parseRecursive(queue));
            }
            if (!queue.isEmpty()) { // 跳过闭合的括号
                queue.poll();
            }
        }

        return node;
    }

    private boolean isOperator(String token) {
        return token.equals("xor") || token.equals("and") || token.equals("not") || token.equals("=");
    }

    public static void main(String[] args) {
        PrefixExpressionParser parser = new PrefixExpressionParser();
        String expression = "(xor (= a 1) (and b (not c)))";
        ExpressionNode root = parser.parse(expression);

        // 打印树结构
        if (root != null) {
            root.printTree("");
        }
    }
}
